from typing import List


class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        size = len(prob)

        # dp[i][j] = 前i个硬币有j个正面朝上的概率
        dp = [[0.0] * (target + 1) for _ in range(size + 1)]
        dp[0][0] = 1.0

        for i in range(1, size + 1):
            for j in range(target + 1):
                dp[i][j] += dp[i - 1][j] * (1 - prob[i - 1])
                if j > 0:
                    dp[i][j] += dp[i - 1][j - 1] * prob[i - 1]

        return dp[-1][-1]


if __name__ == "__main__":
    print(Solution().probabilityOfHeads(prob=[0.4], target=1))  # 0.40000
    print(Solution().probabilityOfHeads(prob=[0.5, 0.5, 0.5, 0.5, 0.5], target=0))  # 0.03125
